package _binary_tree

import org.junit.Assert
import org.junit.Test

/**
 * 2673. 使二叉树所有路径值相等的最小代价
 * 给你一个整数 n 表示一棵 满二叉树 里面节点的数目，节点编号从 1 到 n 。根节点编号为 1 ，树中每个非叶子节点 i 都有两个孩子，分别是左孩子 2 * i 和右孩子 2 * i + 1 。
 * 树中每个节点都有一个值，用下标从 0 开始、长度为 n 的整数数组 cost 表示，其中 cost[i] 是第 i + 1 个节点的值。每次操作，你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。
 * 你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。
 *
 * 注意：
 *
 * 满二叉树 指的是一棵树，它满足树中除了叶子节点外每个节点都恰好有 2 个子节点，且所有叶子节点距离根节点距离相同。
 * 路径值 指的是路径上所有节点的值之和。
 *
 * 示例 1：
 * 输入：n = 7, cost = [1,5,2,2,3,3,1]
 * 输出：6
 * 解释：我们执行以下的增加操作：
 * - 将节点 4 的值增加一次。
 * - 将节点 3 的值增加三次。
 * - 将节点 7 的值增加两次。
 * 从根到叶子的每一条路径值都为 9 。
 * 总共增加次数为 1 + 3 + 2 = 6 。
 * 这是最小的答案。
 *
 *
 * 示例 2：
 * 输入：n = 3, cost = [5,3,3]
 * 输出：0
 * 解释：两条路径已经有相等的路径值，所以不需要执行任何增加操作。
 *
 *
 * 提示：
 * 3 <= n <= 105
 * n + 1 是 2 的幂
 * cost.length == n
 * 1 <= cost[i] <= 104
 */
class leetcode_2672 {
    @Test
    fun test_1() {
        val actual = minIncrements(7, intArrayOf(1, 5, 2, 2, 3, 3, 1))
        val expected = 6
        Assert.assertEquals(expected, actual)
    }

    @Test
    fun test_2() {
        val actual = minIncrements(3, intArrayOf(5, 3, 3))
        val expected = 0
        Assert.assertEquals(expected, actual)
    }

    private fun minIncrements(n: Int, cost: IntArray): Int {
        /**
        题型：二叉树的后序遍历 + 分治法

        思路：
        后序遍历时，先处理叶子节点，把叶子节点变成相同的值，需要多少步
        然后把叶子节点处理，再处理叶子节点的父节点，以此向上。
        那么，向上处理时，每次返回的都是已经处理好的左子树和右子树。

        时间空间度：O（N）
        空间复杂度：O（N）
         */
        collect(n, 1, cost)
        return op
    }

    private var op: Int = 0
    private fun collect(n: Int, i: Int, cost: IntArray): Int { // i ： 节点编号，返回值：路径值
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (2 * i > n) {
            // 叶子节点
            return cost[i - 1]
        }
        // 3 确定单层递归的处理逻辑：后序遍历
        // 左
        val leftPathSum: Int = collect(n, 2 * i, cost) // 获取左子树的路径值

        // 右
        val rightPathSum: Int = collect(n, 2 * i + 1, cost) // 获取右子树的路径值

        // 中
        // 比如，叶子节点 2（i = 4） 和 3（i=5），那么 叶子节点（i = 4）2 需要增加1次
        val minOp = Math.max(leftPathSum, rightPathSum) - Math.min(leftPathSum, rightPathSum)
        op = op + minOp

        //  两个子树的路径值都变成多的那个，再加上i自己的节点值，即为i为根的子树的路径值
        // 比如：叶子节点 2（i = 4） 和 3（i=5）的父节点为5（i = 2）
        return cost[i - 1] + Math.max(leftPathSum, rightPathSum)
    }
}